#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  for (cin >> T; T; T--) {
    int n, k, sum = 0;
    vector<int> num;

    cin >> n >> k;
    for (; n > 0; n /= 3) {
      num.emplace_back(n % 3);
      sum += num.back();
    }
    if (sum > k) {
      cout << "-1\n";
    } else {
      k -= sum;
      for (int i = num.size() - 1; i > 0 && k > 0; i--) {
        int dt = min(k / 2, num[i]);

        num[i] -= dt;
        num[i - 1] += dt * 3;
        k -= dt * 2;
      }
      long long m3 = 1, ans = 0;

      for (int x = 0; x < num.size(); x++, m3 *= 3) {
        ans += num[x] * (m3 * 3 + x * m3 / 3);
      }
      cout << ans << "\n";
    }
  }
  return 0;
}